Content-addressable memory (CAM) is a special type of memory that is used in high-speed search applications. Unlike standard random access memory (RAM) in which data is retrieved by applying an address location, a CAM searches its entire memory to determine whether an applied data word is stored anywhere in the CAM. If the data word is found, the CAM returns a list of one or more storage addresses where the data word was found. Accordingly, a CAM is the hardware embodiment of what in software terms would be called an “associative array”. Because a CAM is designed to search its entire memory in a single operation, it is much faster than RAM in virtually all search applications.
CAM is used in a variety of applications including, for example, central processing unit (CPU) cache controllers, database engines, data compression, artificial neural networks, and computer networking. A typical computer networking application employs a CAM to implement a MAC (Media Access Control) address table in a network router. When the network router receives a data packet at one of its ports, the network updates a CAM-based table with the packet's source MAC address and the port the packet was received on. The destination address is then searched for in the table, to determine what port the data packet needs to be forwarded to.
There are two basic types of CAMs: the binary CAM (BCAM) and the ternary CAM (TCAM). The BCAM is the simplest CAM type. In a BCAM, logic “1” and logic “0” matches are sought for the data that is being compared. In a TCAM, a third logic value, namely, “don't care” can also be used. The “don't cares” in a TCAMs provide the capability of “masking out” bits locally on a bit-by-bit basis (i.e., internal masking). The “don't cares” also allow the entire input/output or one or more CAM columns to be masked out (“global” masking), without requiring the memory logic to perform the compare function for the masked out data.
FIG. 1A is a block diagram of a typical prior art 4×5 bit CAM 10 used in a networking application. The 4×5 CAM 10 comprises an array of CAM cells 100 arranged as four horizontal words, each word being five bits long. The CAM cells 100 contain both storage and comparison circuitry. Search lines 102 run vertically between columns of CAM cells 100 and are used to receive the data to be compared (referred to in the art as “the comparand”) to the CAM cells 100. Matchlines 104 run horizontally between the horizontal words, and indicate whether the bits of the comparand match the bits stored in the CAM cells of any one of the horizontal words. The matchlines 104 may be coupled to inputs of an encoder 106 to generate an address corresponding to a matched word.
FIG. 1B shows a routing table containing a list of destination addresses and corresponding ports, which is implemented in the CAM array shown in FIG. 1A. All four entries in the table are 5-bit words matching both a logic “0” and a logic “1” in that position. Don't care bits are represented by an “X”. Because of the X bits, each of the first three entries in the table represents a range of input addresses. For example, the entry on Line 1 indicates that all addresses within the range 101002-101112 are forwarded to port A.
A CAM search operation begins with precharging all matchlines 104, thereby placing them all temporarily in a match state. Next, the search line drivers 108 drive the search data (i.e. comparand “01101” in the figure) onto the search lines 102. Each CAM cell 100 compares its stored bit against the bit on its corresponding search lines 102. Cells with matching data do not affect the cell's corresponding matchline 104 but cells with a mismatch pull down their corresponding matchlines 104. Cells storing an X operate as if a match has occurred. The aggregate result is that matchlines 104 are pulled down for any word that has at least one mismatch. All other matchlines 104 remain activated (i.e. remain in their precharged). For example, as shown in FIG. 1A, the two middle matchlines 104 remain activated (indicating a match), while the other matchlines 104 discharge to ground, indicating a mismatch. Finally, the encoder 106 generates the search address location of the matching data. In the example, the encoder 106 numerically selects the smallest numbered matchline 104 of the two activated matchlines, generating the match address “01”. This match address is used as the input address to a RAM 20 that contains a list of output ports as depicted in FIG. 2. The match address output of the CAM 10 is used as a pointer, which is used to retrieve associated data from the RAM 20.
The CAM/RAM search can be viewed as a dictionary lookup where the search data is the word to be queried and the RAM contains the word definitions. The router searches for the destination address of each incoming packet in the address lookup table to find the appropriate output port. For example, if the router receives a packet with the incoming address 01101, the address lookup matches both Line 2 and Line 3 in the table. Line 2 is selected since it has the most defined bits, indicating it is the most direct route to the destination.
Prior art CAMs are normally comprised of conventional semiconductor memory (e.g. static random access memory (SRAM)) and comparison circuitry, which enables a search operation to be completed in a single clock cycle. FIG. 3 is a schematic diagram of a prior art BCAM cell 30. The BCAM cell 30 includes a six-transistor (6T) SRAM 300 comprised of two cross-coupled inverters 301 (two transistors each) and two access transistors 302, 304, which are used to read and write the SRAM 300. The access transistors 302, 304 connect the bitlines, BLT and BLB, which are logical complements of one another (i.e. bitline true (BLT) and bitline bar (BLB)), to the storage nodes (QT and QB) of the two cross-coupled inverters 300. The gates of the access transistors 302, 304 are coupled to a wordline (WL).
A CAM cell operates by comparing input data (i.e. the comparand) to the data bit stored in the SRAM. As explained above, CAM cells are typically formed in an array. Each wordline (WL) has a global signal usually referred to as the matchline (ML) associated with it. If there is a match between the data being compared (i.e. the “comparand”) and all of the data bits stored in the array, the corresponding ML will remain high, i.e., will remain in a charged state. If there is a miss to any one bit that is being compared in a row (i.e. there is a mismatch), the corresponding ML to that row will discharge.
Assume for the sake of discussion that the BCAM cell 30 is in static mode (i.e. a mode during which data is not being compared, stored or read from the SRAM cell 300), and that the SRAM 300 has been previously programmed to store a logic “1”. With a logic “1” stored in the SRAM 300, node QB is at 0V (logic “0”) and node QT is at VDD (logic “1”). As a result, transistor 306 is ON and transistor 308 is OFF. Also assume that in static mode, the match line (ML) has also been properly precharged to VDD. Under these conditions, since both bit lines (BLT and BLB) are at 0V, ML is held at the precharged voltage (VDD for example). (Note that in some implementations, BLT and BLB could be precharged to VDD, in which case the source of transistor 310 is also coupled to VDD to maintain the ML high condition in the static mode.)
During a compare operation, the comparand data is inverted and input on the BLT and BLB lines. Assuming again that the data stored in the SRAM 300 is a logic “1”, then if the comparand is also a logic “1”, BLT will be at 0V and BLB will be at VDD (remember that the comparand data is inverted). Accordingly, during the compare operation, transistor 310 will be OFF and the ML will remain charged up to its precharged state, thereby indicating a match if the comparand. On other hand, if during a compare operation the data stored in the SRAM 300 is a logic “1”, and the comparand is a logic “0”, both transistors 306 and 310 are ON and the ML discharges to ground, thereby indicating a miss (i.e. a mismatch of the comparand).
As explained above, typically a CAM array is formed from a plurality of rows of CAM cells. In such a configuration, each row of the array has a common ML, and for each row a multi-bit data comparand is compared to a plurality of data bits stored in the SRAMs of the CAM cells in the row. Accordingly, for the entire length of a given row, if all the bits match the corresponding bits in the comparand, then ML will remain high, thereby indicating a match. If any one of the bits does not match the data store in the corresponding SRAM cell, then the ML for that row will discharge to a logic low level, thereby indicating a mismatch.
FIG. 4 is a schematic diagram of a ternary CAM cell (or “TCAM” cell) 40. The TCAM cell 40 is similar to the BCAM cell 30 shown in FIG. 3, but also includes an additional SRAM cell 400, which is configured to store a don't care bit. The additional SRAM cell 400 implements what is commonly referred to as a “mask bit”. When the SRAM cell 400 is programmed to store a logic “1”, the pull down transistor 402 will always be OFF, irrespective of the data stored in the first SRAM cell 300. Accordingly, under such conditions, the ML will always remain in its precharged state, thereby indicating a don't care during a compare operation.
While prior art BCAMs and TCAMs have come into widespread use, they are plagued with various drawbacks. First, prior art CAMs consume large amounts of both dynamic and static power. Second, prior art CAMs occupy a large area. This large area requirement is mostly attributable to the large areas needed to form the SRAM cells. Third, SRAM-based CAMs are susceptible to radiation induced soft errors. It would be desirable, therefore, to have an improved CAM cell structure that is not plagued with the drawbacks characteristic of SRAM-based CAMs.